/*题目：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。


 * 类似的这种匹配问题，用栈来解决是比较方便的，因为栈本身是先进后出的规则，在匹配方面，根据从字符串中取到的数据，
 * 与从栈中弹出(pop)的数据进行比较，判断是否配对，以及，是否满足配对规则。
 * 字符串中字符如果是'('，'{'，'['就对其进行入栈操作，再对后面的字符进行匹配。
   如果是对应的')'，'}'，']'就对之前入栈的对应括号进行出栈操作，则最后判断stack.isEmpty()是否为空即可。
 * 就本题而言，大致步骤和思想如下： 
 * 1，先行剔除字符个数不是偶数的字符串;
   2，创建Chracter类型的 Stack 对象;
 * 3，对字符串中所有字符的进行遍历配对：
 *    a：从字符串中取出字符，判断字符类型(左侧 or 右侧)后，入栈;
 *    b：针对右侧首先出来的符号进行剔除判断;
 *    c：将栈中字符pop(出栈)，与字符串中数据进行比较;
 * 4，判断栈是否为空；
 */
package javawxy;
import java.util.Stack; //栈类的引用；
class Solution {
	public boolean isValid(String s) {
		if (s.length() % 2 != 0) // 先行判断剔除
			return false;
		Stack<Character> stack = new Stack<>(); // 创建 stack 对象
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if (c == '(' || c == '[' || c == '{') // 入栈
				stack.push(c);
			else {
				if (stack.isEmpty()) // 针对首先出现的右侧符号进行判断
					return false;
				char top = stack.pop(); // 出栈
				if (c == ')' && top != '(') // 对应匹配
					return false;
				if (c == ']' && top != '[')
					return false;
				if (c == '}' && top != '{')
					return false;
			}
		}
		return stack.isEmpty();    // 检查栈是否为空
	}
}